! git log -1 --format="%H"
28688145c190ebc1427f3830d5580e6337c2ebbf
import sys
# Install gurobi
!{sys.executable} -m pip install -i https://pypi.gurobi.com gurobipy
!{sys.executable} -m pip install plotly geopy
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pandas as pd
from itertools import product
import gurobipy as gp
from gurobipy import GRB, quicksum
# These are ours
import problem
import visualization
Looking in indexes: https://pypi.gurobi.com Requirement already satisfied: gurobipy in /opt/anaconda3/lib/python3.8/site-packages (9.1.1) Requirement already satisfied: plotly in /opt/anaconda3/lib/python3.8/site-packages (4.14.3) Requirement already satisfied: geopy in /opt/anaconda3/lib/python3.8/site-packages (2.1.0) Requirement already satisfied: retrying>=1.3.3 in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.3.3) Requirement already satisfied: six in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.15.0) Requirement already satisfied: geographiclib<2,>=1.49 in /opt/anaconda3/lib/python3.8/site-packages (from geopy) (1.50)
def normalize(i, j):
assert i != j
return (i, j) if i < j else (j, i)
from model import Autonomax, Config
# Run on the first |C| cities (mostly for testing)
C = 41
# What scenario we will be utilizing
scenario = 2
# The number of cities in the core net
NC = 3
# 1 if the core net should be a cycle; 0 if it shoul be a path.
Z = 1
autonomax = Autonomax(
Config(
cities=problem.cities[:C],
distances=problem.D[:C, :C],
demand=problem.B[scenario][:C],
core_city_count=NC,
core_net_is_cycle=Z,
)
)
Academic license - for non-commercial use only - expires 2021-05-15 Using license file /Users/sjurwold/gurobi.lic
A = autonomax.model.getA()
count = lambda d: len(d) if isinstance(d, gp.tupledict) else 1
V = sum(count(v) for v in autonomax.variables.values())
C = sum(count(c) for c in autonomax.constraints.values())
print(f'V = {V}, C = {C}')
fig, ax = plt.subplots(1, figsize=(128, 128 * C/V))
ax.set_xticklabels([])
ax.set_yticklabels([])
plt.spy(A)
total = 0
print(f'\nCONSTRAINT SETS:')
for (name, constraint) in autonomax.constraints.items():
constraints_in_set = count(constraint)
print(f'{constraints_in_set:>5} | {name}')
#plt.gcf().text(0.07, 0.69 - 0.4 * (total + 0.5 * count(constraint)) / C, name, fontsize=14)
total += constraints_in_set
plt.plot([0, V], [total - 0.5, total - 0.5], color='grey')
total = 0
print(f'\nVARIABLE SETS:')
for (name, variables) in autonomax.variables.items():
variables_in_set = count(variables)
print(f'{variables_in_set:>5} | {name}')
#plt.gcf().text(0.1 + 0.8 * (total + 0.5*count(variables)) / V, 0.8, name, fontsize=14)
total += count(variables)
plt.plot([total - 0.5, total - 0.5], [0, C], color='grey')
plt.savefig('constraint-matrix.png', dpi=200)
V = 7667, C = 5292
CONSTRAINT SETS:
1 | one_control_center
41 | control_city_directly_connected
1681 | reduce_control_center_symmetry
41 | core_city_ub
1 | cycle_or_path
41 | disallow_core_tree
1 | exactly_nc_core_cities
41 | control_center_is_connected
1640 | is_connectable
82 | is_connected_timestep
41 | connected_graph
41 | conservation_of_flow
820 | force_edge_if_flow
820 | edge_cost_lb
VARIABLE SETS:
41 | is_control_center
820 | is_core_edge
41 | is_core_city
123 | is_connected_step
3362 | is_connectable_step
820 | flow
820 | abs_flow
820 | is_sub_edge
820 | edge_cost
autonomax.model.Params.timeLimit = 1200.0
autonomax.model.optimize()
Changed value of parameter timeLimit to 1200.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 5292 rows, 7667 columns and 25297 nonzeros
Model fingerprint: 0x02f91814
Model has 3 SOS constraints
Model has 820 general constraints
Variable types: 2460 continuous, 5207 integer (5207 binary)
Coefficient statistics:
Matrix range [1e+00, 3e+05]
Objective range [1e+00, 2e+04]
Bounds range [1e+00, 1e+02]
RHS range [7e-01, 4e+01]
Presolve removed 87 rows and 1768 columns
Presolve time: 0.08s
Presolved: 5205 rows, 5899 columns, 25555 nonzeros
Variable types: 2460 continuous, 3439 integer (3439 binary)
Found heuristic solution: objective 117286.47478
Root relaxation: objective 1.155515e+03, 5397 iterations, 0.12 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1155.51469 0 145 117286.475 1155.51469 99.0% - 0s
H 0 0 73614.728610 1155.51469 98.4% - 0s
0 0 1720.13230 0 209 73614.7286 1720.13230 97.7% - 0s
H 0 0 44583.046276 1720.13230 96.1% - 0s
0 0 2516.15753 0 209 44583.0463 2516.15753 94.4% - 0s
0 0 2516.15753 0 209 44583.0463 2516.15753 94.4% - 0s
H 0 0 31718.611787 2516.15753 92.1% - 0s
0 0 2572.57343 0 264 31718.6118 2572.57343 91.9% - 0s
0 0 2579.21254 0 281 31718.6118 2579.21254 91.9% - 0s
0 0 2579.27473 0 306 31718.6118 2579.27473 91.9% - 0s
0 0 2590.18035 0 292 31718.6118 2590.18035 91.8% - 1s
0 0 2592.29831 0 270 31718.6118 2592.29831 91.8% - 1s
0 0 2592.34915 0 270 31718.6118 2592.34915 91.8% - 1s
0 0 2596.81952 0 264 31718.6118 2596.81952 91.8% - 1s
0 0 2607.26047 0 255 31718.6118 2607.26047 91.8% - 1s
0 0 2607.70788 0 259 31718.6118 2607.70788 91.8% - 1s
0 0 2613.70029 0 292 31718.6118 2613.70029 91.8% - 1s
0 0 2614.43503 0 270 31718.6118 2614.43503 91.8% - 1s
H 0 0 24701.468954 2664.65079 89.2% - 1s
0 0 2673.22987 0 307 24701.4690 2673.22987 89.2% - 1s
0 0 2673.22987 0 249 24701.4690 2673.22987 89.2% - 1s
H 0 0 19540.340247 2673.22987 86.3% - 2s
0 2 2673.22987 0 245 19540.3402 2673.22987 86.3% - 2s
H 30 24 19107.793139 2821.51474 85.2% 556 3s
H 70 62 18874.907520 2821.51474 85.1% 322 4s
H 75 62 18762.580732 2821.51474 85.0% 305 4s
H 111 93 18076.090246 2821.51474 84.4% 243 4s
H 114 93 18060.227940 2821.51474 84.4% 251 4s
119 103 3771.53984 16 243 18060.2279 2821.51474 84.4% 252 5s
H 157 125 17991.191179 2821.51474 84.3% 224 5s
H 157 125 17937.725927 2821.51474 84.3% 224 5s
H 162 125 16112.039754 2821.51474 82.5% 217 5s
H 233 174 16068.509142 2821.51474 82.4% 206 6s
H 245 191 16063.139145 2821.51474 82.4% 215 6s
1295 1013 6354.56906 6 184 16063.1391 4572.09421 71.5% 131 10s
1503 1102 4572.09421 13 234 16063.1391 4572.09421 71.5% 135 16s
1557 1117 4572.09421 20 244 16063.1391 4572.09421 71.5% 148 20s
H 1629 1040 15378.840478 4572.09421 70.3% 152 23s
H 1669 977 15326.445943 4572.09421 70.2% 154 23s
H 1710 909 15316.445943 4572.09421 70.1% 155 24s
H 1712 861 15308.978130 4572.09421 70.1% 155 24s
1791 830 cutoff 27 15308.9781 4572.09421 70.1% 155 25s
2541 777 7229.17502 31 198 15308.9781 4572.09421 70.1% 145 30s
2960 771 12106.2027 25 177 15308.9781 7156.64696 53.3% 148 35s
4382 1088 10481.2223 45 122 15308.9781 8347.62386 45.5% 134 40s
H 4782 1285 15195.189396 8677.69538 42.9% 131 41s
H 4924 1277 15077.913727 8776.76152 41.8% 131 41s
6118 1681 10958.6656 47 129 15077.9137 9342.64390 38.0% 126 45s
8556 1498 cutoff 60 15077.9137 10841.9427 28.1% 122 50s
H10306 691 15077.913718 12126.4288 19.6% 119 54s
11231 103 infeasible 51 15077.9137 13710.2986 9.07% 114 55s
Cutting planes:
Gomory: 36
Cover: 89
Implied bound: 10
Clique: 1
MIR: 79
Flow cover: 100
GUB cover: 4
Inf proof: 1
Zero half: 22
RLT: 55
Relax-and-lift: 11
Explored 16104 nodes (1322910 simplex iterations) in 57.41 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 15077.9 15077.9 15195.2 ... 16112
Optimal solution found (tolerance 1.00e-04)
Best objective 1.507791371771e+04, best bound 1.507791371771e+04, gap 0.0000%
city_info = pd.DataFrame(autonomax.city_info())
city_info
| Index | Name | IsCoreCity | IsControlCenter | Demand | IngoingFlow | OutgoingFlow | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | Boden | False | False | 2.3 | 2.800000e+00 | 5.1 |
| 1 | 1 | Borås | False | False | 1.9 | 2.520000e+01 | 27.1 |
| 2 | 2 | Eskilstuna | False | False | 1.3 | 3.900000e+00 | 5.2 |
| 3 | 3 | Falun | False | False | 1.9 | 1.278977e-13 | 1.9 |
| 4 | 4 | Gävle | False | False | 0.7 | 2.610000e+01 | 26.8 |
| 5 | 5 | Göteborg | False | False | 6.4 | 2.273737e-13 | 6.4 |
| 6 | 6 | Halmstad | False | False | 3.4 | 1.160000e+01 | 15.0 |
| 7 | 7 | Haparanda | False | False | 3.9 | 0.000000e+00 | 3.9 |
| 8 | 8 | Helsingborg | False | False | 3.7 | 7.900000e+00 | 11.6 |
| 9 | 9 | Hudiksvall | False | False | 1.3 | 2.230000e+01 | 23.6 |
| 10 | 10 | Jönköping | True | False | 2.9 | 6.530000e+01 | 68.2 |
| 11 | 11 | Kalmar | False | False | 2.8 | 3.552714e-13 | 2.8 |
| 12 | 12 | Karlskrona | False | False | 4.3 | 5.115908e-13 | 4.3 |
| 13 | 13 | Karlstad | False | False | 2.4 | 9.308110e-13 | 2.4 |
| 14 | 14 | Kiruna | False | False | 2.8 | 1.705303e-13 | 2.8 |
| 15 | 15 | Kristianstad | False | False | 4.5 | 6.785683e-13 | 4.5 |
| 16 | 16 | Lidköping | False | False | 0.7 | 8.100000e+00 | 8.8 |
| 17 | 17 | Linköping | True | False | 2.9 | 1.221000e+02 | 125.0 |
| 18 | 18 | Luleå | False | False | 4.4 | 9.000000e+00 | 13.4 |
| 19 | 19 | Malmö | False | False | 4.2 | 3.700000e+00 | 7.9 |
| 20 | 20 | Motala | True | True | 3.1 | 1.315000e+02 | 9.6 |
| 21 | 21 | Norrköping | False | False | 3.4 | 4.710000e+01 | 50.5 |
| 22 | 22 | Nyköping | False | False | 4.4 | 3.750000e+01 | 41.9 |
| 23 | 23 | Sandviken | False | False | 2.5 | 1.200817e-12 | 2.5 |
| 24 | 24 | Skellefteå | False | False | 1.4 | 1.340000e+01 | 14.8 |
| 25 | 25 | Skövde | False | False | 3.1 | 8.800000e+00 | 11.9 |
| 26 | 26 | Stockholm | False | False | 7.7 | 2.980000e+01 | 37.5 |
| 27 | 27 | Sundsvall | False | False | 2.1 | 2.020000e+01 | 22.3 |
| 28 | 28 | Trelleborg | False | False | 3.7 | 1.566747e-12 | 3.7 |
| 29 | 29 | Uddevalla | False | False | 4.0 | 2.273737e-12 | 4.0 |
| 30 | 30 | Umeå | False | False | 1.9 | 1.480000e+01 | 16.7 |
| 31 | 31 | Uppsala | False | False | 3.0 | 2.680000e+01 | 29.8 |
| 32 | 32 | Varberg | False | False | 3.8 | 1.500000e+01 | 18.8 |
| 33 | 33 | Vetlanda | False | False | 0.8 | 1.590000e+01 | 16.7 |
| 34 | 34 | Vänersborg | False | False | 4.1 | 4.000000e+00 | 8.1 |
| 35 | 35 | Västervik | False | False | 3.4 | 2.486900e-12 | 3.4 |
| 36 | 36 | Västerås | False | False | 3.9 | 2.870593e-12 | 3.9 |
| 37 | 37 | Växjö | False | False | 4.3 | 8.800000e+00 | 13.1 |
| 38 | 38 | Örebro | False | False | 2.2 | 4.300000e+00 | 6.5 |
| 39 | 39 | Örnsköldsvik | False | False | 2.5 | 1.670000e+01 | 19.2 |
| 40 | 40 | Östersund | False | False | 1.0 | 9.201528e-13 | 1.0 |
edge_info = pd.DataFrame(autonomax.edge_info())
edge_info
| From | To | Type | Flow | Cost | Distance | |
|---|---|---|---|---|---|---|
| 0 | Skellefteå | Umeå | SUB | 14.8 | 557.326132 | 111 |
| 1 | Eskilstuna | Västerås | SUB | -3.9 | 44.775012 | 43 |
| 2 | Gävle | Hudiksvall | SUB | -23.6 | 966.610215 | 118 |
| 3 | Norrköping | Nyköping | SUB | -41.9 | 595.269663 | 58 |
| 4 | Nyköping | Stockholm | SUB | -37.5 | 1022.500000 | 90 |
| 5 | Karlskrona | Växjö | SUB | 4.3 | 150.077607 | 102 |
| 6 | Linköping | Norrköping | SUB | -50.5 | 476.090652 | 44 |
| 7 | Motala | Örebro | SUB | -6.5 | 191.382381 | 92 |
| 8 | Boden | Kiruna | SUB | -2.8 | 449.539100 | 291 |
| 9 | Sundsvall | Östersund | SUB | -1.0 | 77.633542 | 166 |
| 10 | Halmstad | Helsingborg | SUB | -11.6 | 267.571986 | 79 |
| 11 | Jönköping | Vetlanda | SUB | -16.7 | 286.749284 | 65 |
| 12 | Umeå | Örnsköldsvik | SUB | 16.7 | 627.590973 | 111 |
| 13 | Boden | Luleå | SUB | 5.1 | 39.194104 | 32 |
| 14 | Lidköping | Skövde | SUB | 8.8 | 105.450189 | 49 |
| 15 | Karlstad | Örebro | SUB | 2.4 | 61.279919 | 77 |
| 16 | Halmstad | Varberg | SUB | 15.0 | 258.577201 | 65 |
| 17 | Lidköping | Vänersborg | SUB | -8.1 | 129.045201 | 60 |
| 18 | Uddevalla | Vänersborg | SUB | 4.0 | 22.172747 | 21 |
| 19 | Gävle | Sandviken | SUB | -2.5 | 19.882118 | 25 |
| 20 | Linköping | Motala | CORE | 125.0 | 510.000000 | 51 |
| 21 | Borås | Göteborg | SUB | -6.4 | 131.078630 | 71 |
| 22 | Jönköping | Linköping | CORE | 68.2 | 1250.000000 | 125 |
| 23 | Linköping | Västervik | SUB | -3.4 | 112.715626 | 97 |
| 24 | Sundsvall | Örnsköldsvik | SUB | -19.2 | 878.974055 | 127 |
| 25 | Jönköping | Motala | CORE | -9.6 | 1080.000000 | 108 |
| 26 | Vetlanda | Växjö | SUB | -13.1 | 263.087118 | 72 |
| 27 | Borås | Varberg | SUB | -18.8 | 467.695643 | 84 |
| 28 | Haparanda | Luleå | SUB | 3.9 | 180.293133 | 124 |
| 29 | Luleå | Skellefteå | SUB | 13.4 | 659.953460 | 133 |
| 30 | Stockholm | Uppsala | SUB | -29.8 | 550.119554 | 69 |
| 31 | Kristianstad | Växjö | SUB | 4.5 | 197.061487 | 120 |
| 32 | Gävle | Uppsala | SUB | 26.8 | 403.877951 | 60 |
| 33 | Helsingborg | Malmö | SUB | -7.9 | 126.105814 | 60 |
| 34 | Falun | Örebro | SUB | 1.9 | 125.944766 | 155 |
| 35 | Borås | Jönköping | SUB | 27.1 | 646.341239 | 82 |
| 36 | Jönköping | Skövde | SUB | -11.9 | 284.330749 | 81 |
| 37 | Hudiksvall | Sundsvall | SUB | -22.3 | 524.081992 | 81 |
| 38 | Malmö | Trelleborg | SUB | -3.7 | 33.196374 | 34 |
| 39 | Eskilstuna | Norrköping | SUB | 5.2 | 179.396176 | 102 |
| 40 | Kalmar | Vetlanda | SUB | 2.8 | 124.941927 | 119 |
core_cost = sum(edge_info[edge_info['Type'] == 'CORE']['Cost'])
subnet_cost = sum(edge_info[edge_info['Type'] == 'SUB']['Cost'])
total_cost = core_cost + subnet_cost
print(f'core = {core_cost:>9.3f}')
print(f'subnet = {subnet_cost:>9.3f}')
print('------------------')
print(f'total = {total_cost:>9.3f}')
assert abs(autonomax.model.getObjective().getValue() - total_cost) < 1e-6
core = 2840.000 subnet = 12237.914 ------------------ total = 15077.914
visualization.show(pd.DataFrame(autonomax.city_info()), pd.DataFrame(autonomax.edge_info()))